package study.wy.queue;

/**
 * 优化的队列结构——环形队列
 * @author wy
 */
public class CircleQueue<T> {

    /**
     * 存储元素的数组，需预留一个空位置
     */
    private Object[] circleQueue;

    /**
     * 队列最大容量，由于预留一个空位置，实际最大容量为maxSize-1
     */
    private int maxSize;

    /**
     * 头指针，指向队列头元素所在位置，默认为0
     */
    private int front;

    /**
     * 尾指针，指向队列尾部元素的下一个位置，默认为0
     */
    private int rear;

    public CircleQueue(){
        this(16);
    }

    public CircleQueue(int maxSize){
        this.maxSize = maxSize + 1;
        this.circleQueue = new Object[this.maxSize];
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 判断队列是否已满
     * @return  true：已满，false：未满
     */
    public boolean isFull(){
        /**
         * 1、当数组第一个元素不是头元素时，由于rear指向尾元素的下一个元素并且队列预留了一个空位，所以rear+1即等于front
         * 2、当数组第一个元素是头元素时，此时front=0，且rear+1=maxSize，故取余后相等。
         */
        return (rear + 1) % maxSize == front;
    }

    /**
     * 判断队列是否为空队列
     * @return  true：空队列，false：非空
     */
    public boolean isEmpty(){
        /**
         * 队列为空时，front即指向头元素
         */
        return rear == front;
    }

    /**
     * 添加元素
     * @param obj   添加的元素
     */
    public void add(T obj){
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }
        /**
         * 头指针不动，尾指针+1
         */
        circleQueue[rear] = obj;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 取出头元素
     * @return  取出的头元素
     */
    public T get(){
        if (isEmpty()) {
            throw new RuntimeException("空队列");
        }
        /**
         * 尾指针不动，头指针+1
         */
        T obj = (T) circleQueue[front];
        front = (front + 1) % maxSize;
        return obj;
    }

    /**
     * 展示队列中有效数据
     */
    public void show(){
        if (isEmpty()) {
            throw new RuntimeException("空队列");
        }
        /**
         * 从头元素开始遍历至尾元素
         */
        for (int i = front; i < front + size(); i++) {
            System.out.println(circleQueue[i % maxSize]);
        }
    }

    /**
     * 计算队列中有效数据的个数
     * @return  有效数据的个数
     */
    public int size() {
        return (rear - front + maxSize) % maxSize;
    }

    /**
     * 返回头元素
     * @return  头元素
     */
    public T head() {
        return (T) circleQueue[front];
    }
}
